杭电多校 2019 R6

中国人何必要写英文题面为难中国人 = =

$Salty Fish$

以前写过 ε-(´∀｀; )

$Nonsense Time$

加点 LIS。每次考虑把贡献放到之后所有比自己大的点，管它 ban 没 ban？……QAQ我还是不会树套树意外的解法

离线！分治？不！注意到数据范围有「generated randomly」

随机排列 LIS 期望长度 $\sqrt{n}$

倒做，若删的点在当前 LIS 就重新求 LIS。$O(n\sqrt{n} logn)$

$Code$

$Milk Candy$

写在「拟阵」。奶糖 埃维昂awa! 甜甜

$Speed Dog$

Snowy Smile

首先一定四个边界都有点！好像可以枚举下和右边界的点，预处理上和左边界的点，然后二维数点一只 $log$？好笨啊。

正解：在框定左右边界时线段树维护纵向最大子段和, 一只 $log$。但是清真多了。

简单题想不到……

$x$ 和 $y$ 要分开离散化，不然会 T。

$Code$

$Faraway$

士兵 $10$ 人，坐标 $1e9$，模数 $5$。

考虑拆绝对值，$4^10$ 枚举 $(x_e, y_e)$ 在每个点的哪个方向，确定范围，crt 合并？可以是可以，但是不合法状态太多了，效率太低。

正解清真巧妙：每个点把平面划成四份，共有 $O(n^2)$ 个区域，每个区域到所有点的距离不带绝对值。
枚举区域，然后怎么做？crt 合并？麻烦了。

$lcm(1, 2, 3, 4, 5) = 60$，枚举 $x_e$ 和 $y_e$ 模 $60$ 的余数，$O(n)$ 判合法，$O(1)$ 计算该区域中有多少点，即可。

$O(3600n^3)$

$Code$

$TDL$

心累…… 真正的乱搞题……

$m$ 只有 $1000$。打表可以发现 $f(n, m) - n$ 不超过 $1000$。

设 $p = f(n, m) - n$。$p \oplus n = k$。由于 $p 只有 1000$，影响很小，$n$ 应当在 $k$ 附近，在 $k \pm 1000$ 范围内找一下即可。

$Code$

$11 Dimensions$

中国 ACM 题好没意思…… 完蛋我疯狂脑内循环 Mili 的「我们 在羊水 中漫 步」和「Over (over and over)」怎么办在线等急

Stay Real

模拟当然没什么问题，但是性质是父亲一定比俩儿子小，按「父亲要比儿子后取」的规则最优取，其实就是从大往小取。排序后交替取即可。

$Code$

$Ridiculous Netizens$

事情开始变得有一丢丢意思

统计「$\prod\limits_{x \in G} w_x \leq m$」的连通子树 $G$ 的个数。

首先敏锐的注意到选了 $x$ 就必须选一溜祖先上去，这是个依赖背包问题。$dp_{i, j}$ 表示 dfs 序为 $i$ 的位置之后乘积为 $j$ 的方案数。$m$ 太大了怎么办！$< \sqrt{m}$ 的权值 dp，$> sqrt{m}$ 的权值只能选一个，加一维表示还能取几个 $> \sqrt{m}$ 的。有一种更方便的想法是，把此时乘上那个 $> \sqrt{m}$ 的值得到的 $v$ 变成 $m / v$，此后把乘都表示为除。

这样是 $O(n * n\sqrt{m})$ 的，每个点作为根做一遍 dp 太费啦，我们点分治。

我靠…… 吐了呀 xml 你别再找完 $rt$ 还 $work(y)$ 了！T 疯

$Code$

$Three Investigators$